package com.mj.listen1._08_红黑树.tree;

import java.util.Comparator;

/**
 * 红黑树
 *
 * @param <E>
 */
public class RBTree<E> extends BBST<E> {

    private static final boolean RED = false;
    private static final boolean BLACK = true;

    public RBTree() {
        this(null);
    }

    public RBTree(Comparator<E> comparator) {
        super(comparator);
    }

    /**
     * 给某个节点上色
     *
     * @param node
     * @param color
     * @return
     */
    private Node<E> color(Node<E> node, boolean color) {
        if (node == null) return node;
        // 强转为 RBNode
        ((RBNode<E>) node).color = color;
        return node;
    }

    /**
     * 将Node节点上色为红色
     *
     * @param node
     * @return
     */
    private Node<E> red(Node<E> node) {
        return color(node, RED);
    }

    /**
     * 将Node节点上色为黑色
     *
     * @param node
     * @return
     */
    private Node<E> black(Node<E> node) {
        return color(node, BLACK);
    }

    /**
     * 返回当前节点的颜色
     *
     * @param node
     * @return
     */
    private boolean colorOf(Node<E> node) {
        return node == null ? BLACK : ((RBNode<E>) node).color;
    }

    /**
     * 返回当前节点是否是黑色
     *
     * @param node
     * @return
     */
    private boolean isBlack(Node<E> node) {
        return colorOf(node) == BLACK;
    }

    /**
     * 返回当前节点是否是红色
     *
     * @param node
     * @return
     */
    private boolean isRed(Node<E> node) {
        return colorOf(node) == RED;
    }

    @Override
    protected void afterAdd(Node<E> node) {
        Node<E> parent = node.parent;
        if (parent == null) {
            // 添加的节点是根节点
            black(node);
            return;
        }

        // 如果节点父节点是黑色，直接返回
        if (isBlack(parent)) {
            return;
        }

        // 节点父节点是红色
        // 叔父节点
        Node<E> uncle = parent.sibling();
        // 祖父节点
        Node<E> grand = parent.parent;
        if (isRed(uncle)) {// 叔父节点是红色
            black(parent);
            black(uncle);
            // 把祖父节点当做是新添加的节点
            afterAdd(red(grand));
            return;
        }

        // 叔父节点不是红色
        if (parent.isLeftChild()) {// L
            red(grand);
            if (node.isLeftChild()) {// LL
                // 让祖父节点进行单旋转，染成红色，让父节点成为中心，并染成黑色。
                black(parent);
            } else {// LR
                // 让祖父节点和父节点进行旋转，让新添加成员成为中心节点，染成黑色，祖父节点染成红色。
                black(node);
                rotateL(parent);
            }
            rotateR(grand);
        } else {// R
            red(grand);
            if (node.isLeftChild()) {// RL
                // 让祖父节点和父节点进行旋转，让新添加成员成为中心节点，染成黑色，祖父节点染成红色。
                black(node);
                rotateR(parent);
            } else {// RR
                // 让祖父节点进行单旋转，染成红色，让父节点成为中心，并染成黑色。
                black(parent);
            }
            rotateL(grand);
        }
    }

    @Override
    protected void afterRemove(Node<E> node, Node<E> replaceNode) {
        // 如果删除的节点是红色
        if (isRed(node)) {
            return;
        }

        // 用于取代node的子节点是红色
        if (isRed(replaceNode)) {
            // 直接把取代的节点染成黑色
            black(replaceNode);
            return;
        }

        Node<E> parent = node.parent;
        // 删除的是根节点
        if (parent == null) return;

        // 删除黑色的叶子节点(肯定会下溢)
        // 判断被删除的node是左还是右(如果直接通过sibling()方法,拿到的不准确,因为在remove方法中已经将node置为null了,然后才调用的afterRemove
        // 判断被删除的节点在左边还是右边
        // parent.left == null 被删除节点在左边，node.isLeftChild()表示
        boolean isLeft = parent.left == null || node.isLeftChild();//
        // 拿到兄弟节点
        Node<E> sibling = isLeft ? parent.right : parent.left;
        if (isLeft) {// 被删除的节点在左边，兄弟节点在右边
            if (isRed(sibling)) {// 兄弟节点是红色，旋转为兄弟节点是黑色
                black(sibling);
                red(parent);
                rotateL(parent);
                sibling = parent.right;
            }

            // 走到这里，兄弟节点必然是黑色

            if (isBlack(sibling.left) && isBlack(sibling.right)) {// 表示node的黑兄弟节点的left,right子节点都是黑节点
                // 兄弟节点没有一个红色子节点(不能借一个节点给你), 父节点要向下跟node的兄弟节点合并
                boolean parentBlack = isBlack(parent);// parent是否是黑色
                black(parent);// 父亲染成黑色
                red(sibling);// 兄弟染成红色
                if (parentBlack) {
                    // 如果本身parent是黑色，需要重复执行afterRemove
                    afterRemove(parent, null);
                }
            } else {
                // 表示兄弟节点至少有一个红色子节点,可以向被删除节点的位置借一个节点
                if (isBlack(sibling.right)) {
                    rotateR(sibling);
                    // sibling变更
                    sibling = parent.right;// 因为旋转之后,要更改node的sibling,才能复用下面的染色代码.不然出现bug
                }

                // 统一处理旋转

                // 旋转之后的左右节点染为BLACK。
                color(sibling, colorOf(parent));// 旋转之后的中心节点继承parent的颜色。
                black(sibling.right);
                black(parent);
                rotateL(parent);
            }
        } else {// 被删除的节点在右边，兄弟节点在左边
            if (isRed(sibling)) {// 兄弟节点是红色，旋转为兄弟节点是黑色
                // sibling染成BLACK，parent染成RED，进行旋转。
                black(sibling);
                red(parent);
                rotateR(parent);// 旋转之后,改变兄弟节点,然后node的兄弟节点就为黑色了
                sibling = parent.left;// 兄弟节点变更
            }

            // 走到这里，兄弟节点必然是黑色

            if (isBlack(sibling.left) && isBlack(sibling.right)) {// 表示node的黑兄弟节点的left,right子节点都是黑节点
                // 兄弟节点没有一个红色子节点(不能借一个节点给你), 父节点要向下跟node的兄弟节点合并
                /*
                    首先这里要判断父节点parent的颜色(如果为parent为红色,则根据B树红色节点向其黑色父节点合并原则,parent向下合并,肯定不会
                    发生下溢; 如果parent为黑色,则说明parent向下合并后,必然也会发生下溢,这里我们当作移除一个叶子结点处理,复用afterRemove
                */
                boolean parentBlack = isBlack(parent);// parent是否是黑色
                black(parent);// 父亲染成黑色
                red(sibling);// 兄弟染成红色
                if (parentBlack) {
                    // 如果本身parent是黑色，需要重复执行afterRemove
                    afterRemove(parent, null);
                }
            } else {
                // 表示兄弟节点至少有一个红色子节点,可以向被删除节点的位置借一个节点
                // 兄弟节点的左边是黑色, 先将兄弟节点左旋转; 旋转完之后和后面两种的处理方式相同,都是再对父节点进行右旋转
                if (isBlack(sibling.left)) {
                    rotateL(sibling);
                    // sibling变更
                    sibling = parent.left;// 因为旋转之后,要更改node的sibling,才能复用下面的染色代码.不然出现bug
                }

                // 统一处理旋转

                // 旋转之后的左右节点染为BLACK。
                color(sibling, colorOf(parent));// 旋转之后的中心节点继承parent的颜色。
                black(sibling.left);
                black(parent);
                rotateR(parent);
            }
        }
    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RBNode<>(element, parent);
    }

    /**
     * 红黑树的节点增加自己特有的东西，如颜色
     *
     * @param <E>
     */
    private static class RBNode<E> extends Node<E> {

        private boolean color;

        public RBNode(E element, Node<E> parent) {
            super(element, parent);
        }

        @Override
        public String toString() {
            String str = "";
            if (color == RED) {
                str += "R_";
            }
            return str + element.toString();
        }
    }
}
